package com.LeeCode;

/**
 * 多米诺和托米诺平铺
 */

public class Code790 {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(new Code790().numTilings(n));
    }

    public int numTilings(int n) {
        int mod = 1_000_000_007;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;

        long num1 = 1, num2 = 1, num3 = 2;

        for (int i = 3; i <= n; i++) {
            long aux = (2 * num3 + num1) % mod;
            num1 = num2;
            num2 = num3;
            num3 = aux;
        }
        return (int) num3;
    }
}
